package code1.linkedlist;

/**
 * 原题链接：https://leetcode.cn/problems/reverse-linked-list/
 */
public class P206 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //双指针法翻转链表
    public ListNode reverseList(ListNode head) {
        ListNode cur=head;      //当前节点
        ListNode pre=null;      //前一个节点
        //改变指向
        while(cur!=null){
            ListNode tmp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }

    //递归法翻转链表
    public ListNode reverseList2(ListNode head) {
        return reverse(null,head);
    }

    public ListNode reverse(ListNode pre,ListNode cur){
        if(cur==null){
            return pre;
        }
        ListNode tmp=cur.next;
        cur.next=pre;
        return reverse(cur,tmp);
    }
}
